/*
每次转移时考虑最后一个字符，实际上是对“前缀最优解 + 一步操作”的严格分解

🔎 为什么只看“最后一个字符”就够了？
因为 DP 的思想是：
我们已经知道更小规模问题（前缀更短的转换）的最优解。
要得到更大规模问题（更长前缀的转换），只需要考虑 新加入的最后一个字符 如何处理。
换句话说，编辑距离的最优子结构保证了：

之前的前缀已经最优了；
新的差异只可能出现在最后一个字符；
所以只需要考虑“最后一个字符相等/不等”时的三种操作。
*/

/*
📐 更严谨的表述
当 word1[i-1] != word2[j-1] 时：

替换： 把 word1[0..i-2] 变成 word2[0..j-2]（代价 dp[i-1][j-1]）， 然后再把 word1[i-1] 替换成 word2[j-1]（+1）。
删除： 把 word1[0..i-2] 变成 word2[0..j]（代价 dp[i-1][j]）， 然后删掉 word1[i-1]（+1）。
插入： 把 word1[0..i] 变成 word2[0..j-2]（代价 dp[i][j-1]）， 然后在末尾插入 word2[j-1]（+1）。

🧩 举例验证
word1 = "ab", word2 = "acb"

计算 dp[2][3]（"ab" → "acb"）：
替换：dp[1][2] + 1 = 把 "a" → "ac"，再替换 "b" → "b"（其实不用替换，代价更大）。
删除：dp[1][3] + 1 = 把 "a" → "acb"，再删 "b"。
插入：dp[2][2] + 1 = 把 "ab" → "ac"，再插入 "b" ✅。
最优解就是插入。
*/
//1.二维dp

class Solution {
public:
    int minDistance(string word1, string word2) {
        int m = word1.size();
        int n = word2.size();
        vector<vector<int>> dp(m+1, vector<int>(n+1, 0));

        for(int i=0;i<=m;++i){
            dp[i][0]=i;  //dp[i][0] = i → 把 word1 前 i 个字符变成空串，需要删除 i 次
        }
        for(int j=0;j<=n;++j){
            dp[0][j]=j;  //dp[0][j] = j → 把空串变成 word2 前 j 个字符，需要插入 j 次
        }
        for(int i=1;i<=m;++i){
            for(int j=1;j<=n;++j){
                if(word1[i-1] == word2[j-1]) {
                    dp[i][j] = dp[i-1][j-1];  //（最后一个字符相同，不需要额外操作）
                }
                else {
                    dp[i][j] = min(dp[i-1][j-1] + 1, min(dp[i-1][j] + 1, dp[i][j-1] + 1));
                    /*
                        dp[i-1][j-1] + 1 → 替换
                        dp[i-1][j] + 1 → 删除
                        dp[i][j-1] + 1 → 插入
                    */
                }
            }
        }
        return dp[m][n];
    }
};

//2.一维dp
class Solution {
public:
    int minDistance(string word1, string word2) {
        int m = word1.size();
        int n = word2.size();
        
        vector<int> dp(n+1, 0);
        for(int j=0;j<=n;++j){
            dp[j]=j;
        }
        for(int i=1;i<=m;++i){
            int prev = dp[0]++;  //因为二维的第一列是从0每次增加1，所以要++，相当于dp[i-1][0]
            for(int j=1;j<=n;++j){
                int temp = dp[j];
                if(word1[i-1] == word2[j-1]) {
                    dp[j] = prev;
                }
                else {
                    dp[j] = min(prev + 1, min(dp[j] + 1, dp[j-1] + 1));
                }
                prev = temp;
            }           
        }
        return dp[n];
    }
};